We have shown only the "If" part of own statement.
To prove the "only if" part, we note
for r=1,Gn=a(x+1)→+∞ as x→+∞
so {Gn}n=0+∞ does not have a limit (it diverges to +∞ ) and ∑k=0+∞a(1)k is divergent,
If ∣r∣>1, one can show that limn→+∞(rn+1) does not exist sene if r>1, these terms get larger and largen positively, while if r<−1,rn+1 gets larger and larger in absolute value and it switches from positive to negative and so cant have a limit EXERCISE: What happens when r=−1 ? ∥ (16)
Principle of Mathematical Induction (P.M.I.)
Couscher a formal sequence of propositional functions {P(n)}n=1+∞.
We want to be able to prove that the proposition ∀xP(x) is True where the universe of discourse for the universal quantifier, ∀, is Z+.
As some examples of such a proposition we have the 3 summation formulae from before,
(1) ∑k=1nk=2n(n+1),∀n+Z+
(2) ∑k=1nk2=6n(n+1)(2n+1),∀n∈Z+
(3) ∑k=1nk3=[2n(n+1)]2,∀n∈Z+
We prove such universally quantified propositions using P.M.I. (7)
P.MI. has 2 steps.
Steel Basis step; prove P(1) is true.
Step 2 Inductrie step; prove that the proposition
∀k(P(k)→P(k+1))(k≥1)
is tue.
We will prove the validity of PMI. later.
For now consider some examples. At the some time we will be proving useful and important results.
ExT Prove statement (1) above. [ Note, we already gave a direct proof by showing P(x) is T, fox all x,]
Let P(n) be the statement
k=1∑nk=2n(n+1)=f(n)
Basis Step P(1):∑k=11k=1,f(1)=21(1+1)=1
∴P(1) is tue. (18)
Inductive step
assume Pk(k) is tue, k∈Z+(k⩾1)
That is ∑l=1kl=2k(k+1)=f(k).
We show now that P(k+1) io tue, ie, ∑k=1k+1l=f(k+1)
But ∑l=1k+1l=∑ℓ=1kl+(k+1)
(=2(k+1)(k+2))=2k⋅k+1)+(k+1), by hypothesis. =(k+1)(2k+1)=2(k+1)(k+2)=f(k+1)
=6k(k+1)(2k+1)+(k+1)2, by =(k+1)[6k(2k+1)+k+1]=(k+1)[62k2+k+6(k+1)]=(k+1)[62k2+7k+6]]=6(k+1)[2k2+4k+3k+6]+6(k+1)[2k(k+2)+3(k+2)]= hypoth (k+1)(k+2)(2k+3)=f(k+1)
∀k∈Z+
Thus ↑P(k)→P(k+1) is tue and by PMI
P(n) is tue, ∀n+Z+(20)
Notes 1) a common err in proofs using PMI that lead to an invalid conclusion occurs in the inductive step when we prove P(k)→P(k+1) is true for k=2,3,4,…, and not for k=1. Then there is no connection between the basis step and the inductive step. This will occur when we have to assume k>1 in a der to prove P(k)→P(k+1) If P(2) is false, then we cant conclude ∀nP(n).
We may use PMI to prove ∀n⩾n0,P(n) is tue where n0>1 by changing the basis step to P(n0) is True, and the inductive step to ∀k⩾n0,P(k)→P(k+1)
Ex 3 Recall the Harmonic Progression {an}n=1∞ where an=n1.
Even though,
n→+∞liman=n→+∞limn1=0,
the Harmonic series ∑n=1+∞n1=1+21+31+⋯+n1+⋯ io divergent. (The smaller * smaller bit added infinitely often add up to +∞.1 ) (2)
We will use PMI to help prove this fact Lemma Let Hn=∑k=1nk1.
Then H2⩾1+2x=f(x),∀n∈Z+
Proof
Basis step
x=1H2′=1+21=f(1)∴H2⩾f(1)
Inductive Step
assume H2k⩾1+2k,∀k∈Z+
Then
H2k+1=k=1∑2k+1k1=r=1∑2kr1+k=2k+1∑2k+1r1⩾1+2k+2k+11+2k+21+⋯+2k+11=1+2k+2k+11+2k+21+⋯+2k+2k1⩾1+2k+{2k+2k1+⋯+2k+2k2k terms }⎝⎛ make the portico bergen hechion get smaller ⎠⎞=1+2k+2k⋅2k+11=1+2k+21=1+2k+1=f(k+1)
(22)
Thus by P,M.1. H2n⩾1+2n,∀n∈Z+
Now the sequence
{Hn}n=1∞ is an "increasing" sequence
because Hn+1=Hn+n+11>Hn.
Also the subsequence
{H2n}x=1∞ clearly, in view of
the lemma, has
x→+∞limH2x=+∞
These two facts allow us to assent that
n→+∞limHn=+∞ and the
hamonic series is divergent
Exerciser) Use PMI to prove that 3/22n−1,∀x∈Z+
Prove summation formula (3)
P351 #32 3∣n3+2n∀n⩾1
23
P(n):3∣n3+2n R.T.P. ∀n⩾1P(n) is the
Basis step
Let n=1,n3+2n=1+2=3+3/3
∴P(1) is true
Inductive Step
want to show
∀k⩾1P(k)→P(k+1) is tue
Assume 31k3+2k ie assume P(k) is the
Then (k0+1)3+2(k+1)=k3+3k2+3k+1
==k3+2k+3k+2 divisible by k3+2k+ divisible by 33(k2+k+1)